home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48hor1 / dec2frac.doc < prev    next >
Text File  |  1995-03-31  |  3KB  |  82 lines
  1. DEC2FRAC for the HP 48SX (faster and more complete than ->Q) 
  2. Improved Decimal-to-Fraction, by Joseph K. Horn, 21 March 1991 
  3. (Not as short or fast as D2F, but this one's readable.) 
  4.  
  5.  
  6. THE PROBLEM: The HP 48SX (->Q function) and HP 32SII (with maximum denominator 
  7.   set) both miss many solutions, and slowly recalculate the summations for each 
  8.   term rather than using a fast recursion formula to get each term from the 
  9.   last two. 
  10.  
  11.  
  12. THE SOLUTION: This new algorithm finds the very best solution, very quickly. 
  13.  
  14.  
  15. ALGORITHM: Continued Fractions by fast recursion formula, then make a single 
  16.   calculated jump backwards to the best possible fraction before the specified 
  17.   maximum denominator. 
  18.  
  19. Copyright (c) 1991 by Joseph K. Horn.  May be used freely in any application 
  20.   that has no documentation.  May be in a documented application if the above 
  21.   author is credited. 
  22.  
  23.  
  24. INPUT: 
  25.  
  26. 2: Decimal Number to be converted to a fraction 
  27. 1: Maximum Allowed Denominator (a positive integer) 
  28.  
  29.  
  30. OUTPUT: 
  31.  
  32. 1: 'Numerator/Denominator' 
  33.  
  34. Note: System flag -3 is cleared (to allow symbolic results). 
  35.  
  36.  
  37. EXAMPLE of completeness: What fraction is closest to the number "e", but with a 
  38.   denominator not bigger than 20? 
  39.  
  40. The HP 48SX and the HP 32SII say it's 19/7.  They both say that the next better 
  41.   fraction is 87/32.  But there are two fractions between these which they 
  42.   miss: 49/18 and 68/25. 
  43.  
  44. Press 1 EXP 20 DEC2FRAC and see '49/18', the correct answer. 
  45.  
  46.  
  47. EXAMPLE of speed improvement: the golden ratio, (û5+1)/2, which is 
  48.   approximately 514229/317811.  This is found by the HP 48SX ->Q function in 
  49.   3.23 seconds, and by DEC2FRAC in 1.29 seconds.  For the fastest possible 
  50.   program, see D2F on this disk, which finds it in 0.86 seconds. 
  51.  
  52. ------------ 
  53.  
  54. At the March 22nd meeting of the Orange/Los Angeles Counties Chapter of the 
  55. HP-48 users club, Harry Bertucelli objected to my contention that DEC2FRAC 
  56. finds ALL possible fractions. 
  57.  
  58. Harry is a professional mathematician, and accepts nothing without a formal 
  59. proof.  So he withdrew to a corner of the room and into a deeper corner of his 
  60. mind, and in short order developed a complete proof that DEC2FRAC does in fact 
  61. find all possible fractions (up to the point where the HP 48 begins to 
  62. introduce round-off errors, of course).  It made his day to see (and prove the 
  63. validity of) a completely new algorithm in number theory.  It made my day to 
  64. know that the very first computer to run it was an HP 48SX. 
  65.  
  66. ------------ 
  67.  
  68. Well, darn it, this is only half true.  It may well be that the 48 has the 
  69. honors, but the algorithm IS NOT NEW. 
  70.  
  71. Bummer.  I thought I'd discovered something new.  Turns out that I was 102 
  72. years late!!  In a book called _Textbook of Algebra_ by G.  Chrystal, 1st 
  73. edition in 1889, in Part II, Chapter 32, this improved continued fraction 
  74. algorithm is presented and proven.  Odd to tell, Chrystal speaks of it as if it 
  75. were ancient knowledge.  The original discoverer is not named, nor is the 
  76. algorithm.  Hmmm.  Thanks to Harry Bertucelli for exhuming this obscure 
  77. reference.  In any case, it seems to have lay dormant for many years; it is not 
  78. mentioned in modern books about number theory.  It's time for us to revitalize 
  79. it! 
  80.  
  81. [See NEW2Q for HP's reaction to DEC2FRAC.  -jkh-] 
  82.